package com.cqs.leetcode.link;

import com.cqs.leetcode.ListNode;
import com.cqs.leetcode.Node;

import java.util.*;

public class ReorderList143 {

    /**
     * 快慢指针+栈
     * @param head
     */
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode slow = head, fast = head.next;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            }
        }
        //flow之后的部分是要反转的
        ListNode revert = slow.next;
        //断开 防止新的链表组成环
        slow.next = null;

        Stack<ListNode> stack = new Stack<>();
        while (revert != null) {
            stack.push(revert);
            revert = revert.next;
        }
        //开始生成新的链表
        ListNode node = head;
        while (stack.size() > 0) {
            ListNode lNext = node.next;
            stack.peek().next = lNext;
            node.next = stack.pop();
            node = lNext;
        }
    }

    ListNode result = null;
    public ListNode reverseList(ListNode head) {
        revert(head);
        return result;
    }

    private ListNode revert(final ListNode head){
        if(head == null || head.next == null) return result = head;
        ListNode node =  revert(head.next);
        head.next = null;
        if(node != null) {
            node.next = head;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node.next = node2;
        node2.next = node3;

        ReorderList143 rc = new ReorderList143();
        ListNode listNode = rc.reverseList(node);
        System.out.println(listNode);

    }

    public Node cloneGraph(Node node) {
        Queue<Node> q = new LinkedList<>();
        q.add(node);
        Set<Integer> set = new HashSet<>();
        Node g = null;
        Map<Integer,Node> map = new HashMap<>();
        while(q.size() > 0){
            node = q.poll();
            //防止重复处理节点
            if(set.contains(node.val)) continue;
            set.add(node.val);
            //复制当前节点
            Node t = map.computeIfAbsent(node.val, k -> new Node(k));
            if(g == null) g = t;
            List<Node> list = new ArrayList<>();
            for(Node n: node.neighbors){
                Node ns = map.computeIfAbsent(node.val, k -> new Node(k));
                list.add(ns);
            }
            t.neighbors = list;
            q.addAll(node.neighbors);
        }
        return g;
    }
}
